<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>数据结构之单向链表</title>
</head>
<body>
  <script type="text/javascript">
    // 节点类
    function Node(data) {
      this.data = data;
      this.next = null;
    }

    // 链表类
    function LinkList() {
      this.head = new Node('head');
      this.find = find;
      this.insert = insert;
      this.findPrev = findPrev;
      this.remove = remove;
      this.display = display;
    }

    // 找到当前节点
    function find(data) {
      var currentNode = this.head;
      while (currentNode.data !== data) {
        currentNode = currentNode.next;
      }
      return currentNode;
    }

    // 在当前节点之后插入新节点
    function insert(newData, data) {
      var newNode = new Node(newData);
      var currentNode = this.find(data);
      newNode.next = currentNode.next;
      currentNode.next = newNode;
    }

    // 找到当前节点的前驱节点
    function findPrev(data) {
      var currentNode = this.head;
      while (currentNode.next && currentNode.next.data !== data) {
        currentNode = currentNode.next;
      }
      return currentNode;
    }

    // 删除某个节点
    function remove(data) {
      var prevNode = this.findPrev(data);
      var currentNode = this.find(data);
      if (prevNode.next) {
        prevNode.next = currentNode.next;
        currentNode.next = null; // 释放内存，防止内存泄漏
      }
    }

    // 打印整个链表
    function display() {
      var currentNode = this.head;
      var linkArr = [];
      while (currentNode.next) {
        // 打印链表时不需要打印头节点
        linkArr.push(currentNode.next.data);
        currentNode = currentNode.next;
      }
      console.log(linkArr.join(' -> '));
    }

    var link = new LinkList();
    link.insert('first', 'head');
    link.insert('second', 'first');
    link.insert('third', 'second');
    link.display();
    link.remove('second');
    link.display();
  </script>
</body>
</html>